HW#5 --- last modified February 28 2019 22:32:06..

Solution set.

Due date: Nov 24

Files to be submitted:
  Hw5.zip

Purpose: To gain experience with a strongly-typed functional programming language by experimenting with ML. To learn about recursive types, to experiment with polymorphism.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

(9)[Understand type systems].

Specification:

Your zip file should contain a file code.sml with all your ML code. The grader will look at this code and then load it into interactive mode and experiment with it. Any additional instructions you want to give the grader should be in a file readme.txt which also should be in the zip file. To start for this homework I'd like you to create a new datatype tern (short for ternary). It should have values YES, NO, and MAYBE. Next I want you to create a recursive datatype tern formula. It should have constructors AND, OR, NOT, and INPUT. AND and OR take two tern formulas as arguments, NOT takes a single tern formula as argument, and INPUT takes a tern as argument. You should create three values: a,b,c of type tern formula, each of these should make use of all four constructors listed above. Next you should make a function tern_eval from tern formulas to terns and test it out on your three values. tern_eval should operate as follows, if A is a tern formula of form:

• INPUT(t), tern_eval returns the tern t.
• NOT(B), tern_eval computes v = tern_eval(B), if this is YES, output NO, and vice-versa; if v is MAYBE output MAYBE.
• AND(C,D), tern_eval computes v = tern_eval(C), and w=tern_eval(C), if both v,w are YES output YES, if either are NO output NO; otherwise output MAYBE.
• OR(C,D), tern_eval computes v = tern_eval(C), and w=tern_eval(C), if either of v,w is YES output YES, if both are NO output NO; otherwise output MAYBE.

For second experiment with types, you will test out ML's ability to create polymorphic functions by creating a function make_palindrome of type 'a list which takes a list and appends to it the reverse of the list. Then test your function on string lists, int lists, and bool lists. As an example, on input [1, 2, 3] the output would be: [1, 2, 3, 3, 2, 1].

For the last part of the assignment, consider the description of how polymorphic type inference works in the book. Give an example of an expression where you think type inference will take more than linear time in the expression. Try to figure out an example which would illustrate the worst case run-time of the type inference algorithm. Put your answer to this part of the assignment in your readme.txt file.

Point Breakdown